2014年硕士研究生入学考试初试考试大纲
科目代码：809
科目名称： 运筹学
适用专业： 交通运输工程、交通运输规划与管理
参考书目：[1] 《管理运筹学》大连理工大学出版社2006.6
[2] 《运筹学》（修订版）清华大学出版社 2003.6
考试时间：3小时
考试方式： 笔试
总 分： 150分
考试范围：
一、 线线规划与单纯形法
线性规划问题和数学模型、线性规划图解法、线性规划解的性质、单纯形法及人工变量单纯形法
二、对偶理论与灵敏度分析
线性规划问题的对偶及其变换、线性规划的对偶定理、对偶单纯形法、 线性规划的灵敏度分析
三、运输问题
运输问题的数学模型的特点及其求解、不平衡的运输问题的求解、运输问题的应用
四、整数规划
整数规划问题数学模型的特点及其求解思路、整数规划问题的求解方法、 指派问题及其求解方法
五、动态规划
动态规划模型的最优性原理及其算法基本思路、离散型动态规划模型特点及其求解、连续型动态规划模型特点及其求解
六、图与网络分析
图和网络的基本概念、 树和最小生成树、最短路径问题的求解、 网络最大流、最小截集的求解、最小费用最大流的求解
七、 随机服务理论概述
随机服务系统的基本组成、 生灭过程的概念及其稳态解、 泊松输入--指数服务排队系统特点及其计算、 排队系统的优化设计
样 题：
一、（28分）已知线性规划问题：
当t1=t2=0时，求解得最终单纯形表如下
XB B-1b x1 x2 x3 x4 x5
x3 3/2 0 1/2 1 1/2 0
x1 5/2 1 -1/2 0 -1/6 1/3
Zj-Cj 0 4 0 4 2
试分别进行下面的计算
1、当t2=0时，t1在什么范围内变化上述最优基不变？（6分）
2、当t2=2，t1=5,a21= -4，a22=1时最优解如何变化？（10分）
3、若t1=t2=0时，x1，x2，x3取整数，最优解如何？（12分）
二、（22分）已知线性规划问题
最优单纯形表如下：
XB B-1b x1 x2 x3 x4 x5
x1 1 1 0 -1 4 -1
x2 2 0 1 2 -1 1
Zj-Cj 0 0 3 5 1
1、 写出其对偶问题。（18分）
2、 给出对偶问题的最优解，说明其理论依据。（4分）
三、（32分）有三个产地A1、A2、A3生产同一种物品，使用者为B1、B2和B3，各产地和需求地的需求量以及运输单价如下表。由于销售需要和客观条件限制，B1至少要收到6个单位，它最多需要10个单位，B2必须收到4个单位，B3至少收到6个单位，如表所示。试进行下列分析
1、建立表式运输模型。（10分）
2、判断运输方案可行的条件是什么？请给出本题的一个可行方案。（11分）
3、判断上题方案的最优性，若不是最优则求最优方案。（7分）
4、判断最优方案的多重性，若是多重解，再写出一个最优方案。（4分）
B1 B2 B3 a
A1 2 4 3 11
A2 1 5 6 7
A3 3 2 4 4
b 6≤b≤10 b=4 b6
四、（26分）某工厂生产三种产品，产品重量与利润关系如下表所示，现将三种物品运往市场，运输能力总重量不超过12吨,且每种物品至少运输一件。若利用动态规划求解，试进行下列分析：
物品 重量（吨/件) 利润（百元/件）
1 2 80
2 3 130
3 4 180
1、确定状态变量和边界条件并试述分析过程。（6分）
2、求解运输多少件才能使总利润最大。（20分）
五、（10分）某街口汽车加油站同时可为一辆车加油，还可容纳二辆汽车等待，超过此限则顾客不能等待而离去。汽车到达间隔与加油时间均为指数分布，平均每小时到达8辆车，平均加油时间为每辆6分钟。求每辆汽车的平均逗留时间和潜在顾客损失率。
六、（22分）有如下网络图，图中弧上权重为(容量，费用)，试求最小费用最大流。
七、（10分) 某运输队有4辆汽车驶往3个目的地送货，一地的货物只需一辆汽车运输，其运费见下表所示，若汽车2载不下A地所需货物，汽车4载货是爬不上通往B地必经上坡，试求最优的调运方案。
表4 运输费用表
目的地 汽车1 汽车2 汽车3 汽车4
A 10 - 14 11
B 13 20 23 -
C 8 6 10 7
